CODv2 3.10 包括的な例題解説

from CODv2 第3章「命令：マシンの言葉」

CODv2 3.10 包括的な例題解説

C 言語で組んだプログラムから MIPS のアセンブリ・コードを導出する

swap 手続き

メモリ中の2つのロケーションの内容を入れ替える C 言語の手続き

swap 手続き

code:exp3.10.1.c

swap(int v[], int k)

{

int temp;

temp = vk;

vk = vk + 1;

vk + 1 = temp;

}

swap 手続きでのレジスタの割り付け

3.6 コンピュータ・ハードウェア内での手続きのサポート

「手続き呼び出しの間に、保持されるレジスタと保持されないレジスタ」 CODv2 第3章「命令：マシンの言葉」#6850f43e0000000000b18d39

MIPS の規約では手続きへのパラメータの引き渡しに(引数)レジスタ $a0 から $a4 を使用する

swap 手続きではパラメータは v と k の2つを使用する

それぞれに $a0 と $a1 を割り付ける

その他、使用するパラメータは temp

一時レジスタ $t0 を割り付ける

これらのレジスタ割り付けは、この swap 手続きの最初の変数宣言に相当する

swap(int v[], int k)

int temp

!? 変数宣言って、レジスタ割り付けだったのかーー

swap 手続き本体のコード

残りの部分

temp = v[k]

v[k] = v[k+1]

v[k+1] = temp

配列 v[] のベースアドレスから v[k] のアドレスを得るステップ

語のサイズは4バイト

語アドレスは4バイト刻み

インデックスは 0 始まり

インデックス k を4倍する

$t1 に配列 v のベースアドレス

code:exp3.10.1.asm

# 手続き本体

add $t1, $a1, $a1 # パラメータ k ($a1)、k * 2 をレジスタ $t1 に代入

add $t1, $t1, $t1 # k * 4 をレジスタ $t1 に代入

add $t1, $a0, $t1 # パラメータ v ($a0) ［配列 v のベースアドレス］、v + (k * 4) を $t1 に代入

# レジスタ $t1 は vk のアドレスを表す

v[k] と v[k+1] をロード

$t1 を使って v[k] をロードする

$t1 に4を加算して v[k+1] をロードする

code:exp3.10.1.asm

lw $t0, 0($t1) # vk を temp ($t0) へ代入

lw $t2, 4($t1) # vk+1 を一時レジスタ $t2 へ代入

# v[] の次の要素を呼び出し

アドレスを入れ替えてそれぞれの語をストアする

code:exp3.10.1.asm

sw $t2, 0($t1) # vk に一時レジスタ $t2 を代入

sw $t0, 4($t1) # vk+1 に temp ($t0) を代入

戻り

code:exp3.10.1.asm

# 戻り

jr $ra # 呼び出し元のルーチンに戻る

レジスタの退避

これでメモリ領域の割り付け、手続き内容のコーディングが終了

残っているのは swap 手続き内で使用されるレジスタを退避するためのコーディングであるが、このリーフ手続きでは保持すべきレジスタを使用しないので、レジスタを退避する必要がない

手続き呼び出しの間に、保持されるレジスタと保持されないレジスタ CODv2 第3章「命令：マシンの言葉」#6850f43e0000000000b18d39

https://gyazo.com/03013b39454be75c0523f3f015ae11a8

swap 手続きの全体をまとめると

code:exp3.10.1.a.asm

swap: add $t1, $a1, $a1 # パラメータ k ($a1)、k * 2 をレジスタ $t1 に代入

add $t1, $t1, $t1 # k * 4 をレジスタ $t1 に代入

add $t1, $a0, $t1 # パラメータ v ($a0) ［配列 v のベースアドレス］、v + (k * 4) を $t1 に代入

# レジスタ $t1 は vk のアドレスを表す

lw $t0, 0($t1) # vk を temp ($t0) へ代入

lw $t2, 4($t1) # vk+1 を一時レジスタ $t2 へ代入

# v[] の次の要素を呼び出し

sw $t2, 0($t1) # vk に一時レジスタ $t2 を代入

sw $t0, 4($t1) # vk+1 に temp ($t0) を代入

jr $ra # 呼び出し元のルーチンに戻る

sort 手続き

code:exp3.10.2.c

sort(int v[], int n)

{

int i, j;

for(i = 0; i < n; i = i + 1){

for(j = i - 1; j >= 0 && vj > vj + 1; j = j - 1){

swap(v, j);

}

挿入ソート

ソートの基本アルゴリズムは、バブルソート、挿入ソート、選択ソート

これは「挿入ソート」

https://ja.wikipedia.org/wiki/挿入ソート

挿入ソート（そうにゅうソート、英: insertion sort）あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。

https://www.codereading.com/algo_and_ds/algo/insertion_sort.html

https://gyazo.com/067032cf26038ad1ef02acd21693f342

swap 手続き CODv2 第3章「命令：マシンの言葉」#68637b870000000000e0f388

swap(v, j) は v[] の j 番目の語と、その次の j+1 番目の語を入れ替える

sort 手続きでのレジスタの割り付け

2つのパラメータ v, n に、引数レジスタ $a0, $a1 を割り付ける

変数 i, j には退避レジスタ $s0, $s1 を割り付ける

sort 手続き本体のコード

2重の for ループと swap 手続きの呼び出しで構成される

swap 手続きにはパラメータが2個、付随する

1番目の for ループ

code:exp3.10.2a.c

for(i = 0; i < n; i = i + 1){ }

for 文の構成は、1)カウンタの初期化、2)ループの終了判定、3)繰り返し時のカウンタ繰り上げ

1)初期化

code:exp3.10.2a.asm

move $s0, $zero # i =0

move は疑似命令( CODv2 3.9 プログラムの起動#68db92770000000000937d76 )

2)ループの終了判定

i < n が真でないとき、ループを終了

→ i >= n のとき、ループから抜ける

$s0 < $a1 のとき $t0 に 1 を設定、そうでないときに 0 を設定する

$s0 >= $a1 のときにループを終了する( $t0 が 0 のときループの出口に分岐)

code:exp3.10.2a.asm

for1tst: slt $t0, $s0, $a1 # i >= n ($s0 >= $a1) のとき $t0 = 0

beq $t0, $zero, exit1 # i >= n ($s0 >= $a1) のとき exit1 へジャンプ

3)カウンタ繰り上げ

code:exp3.10.2a.asm

addi $s0, $s0, 1 # i = i + 1

add immediate 命令 ( CODv2 第3章「命令：マシンの言葉」#6874bc5b0000000000769b56 )

4) ループの最後でループの先頭に戻る

code:exp3.10.2a.asm

j for1tst # 外側のループの最初に戻る

ext1:

1番目の for ループをまとめると

code:exp3.10.2a-all.asm

move $s0, $zero # i =0

for1tst: slt $t0, $s0, $a1 # i >= n ($s0 >= $a1) のとき $t0 = 0

beq $t0, $zero, ext1 # i >= n ($s0 >= $a1) のとき exit1 へジャンプ

...

(1番目の for ループの本体)

...

addi $s0, $s0, 1 # i = i + 1

j for1tst # 外側のループの最初に戻る

exit1:

2番目の for ループ

code:exp3.10.2b.c

for(j = i - 1; j >= 0 && vj > vj + 1; j = j - 1){ }

1)初期化

code:exp3.10.2b.asm

addi $s1, $s0, -1 # j = i - 1 (つまり j = i + (-1) )

2)ループの終了判定

2つの条件判定からなる

a) j >= 0 の場合

b) v[j] > v[j + 1] の場合

a) , b) 両方の条件が成り立つ場合、ループが継続される

→ a), b) いずれかの条件が満たされない場合、ループから抜ける

a) の条件判定

j >=0 が真でないとき、ループを終了

→ j < 0 のとき、ループから抜ける

$s1 < 0 のとき $t0 に 0 を設定する( slti 命令 CODv2 第3章「命令：マシンの言葉」#688318520000000000d1423a )

code:exp3.10.2b.asm

for2tst: slti $t0, $s1, 0 # $s1 < 0 (つまり j < 0 )のとき $t0 = 1

bne $t0, $zero, exit2 # $s1 < 0 (つまり j < 0 )のとき exit2 へジャンプ

ここで exit2 へ分岐すると2番目の条件判定を飛び越す

j >= 0 の場合は2番目の条件判定へ進む

b) の条件判定

v[j] > v[j + 1] の真偽を判定し、偽の場合、ループから抜け出る

v[j] のアドレスを算出する

j を4倍して、ベースアドレス v[] に加算する

code:exp3.10.2b.asm

add $t1, $s1, $s1 # $t1 = j * 2

add $t1, $s1, $s1 # $t1 = j * 4

add $t2, $a0, $t1 # $t2 = v + (j * 4)

# レジスタ $t2 は vj のアドレスを表す

v[j] をロードする

code:exp3.10.2b.asm

lw $t3, 0($t2) # $t3 = vj

v[j + 1] をロードする

code:exp3.10.2b.asm

lw $t4, 4($t2) # $t4 = vj + 1

v[j] > v[j + 1] が偽の場合、ループから抜け出る

→ v[j] <= v[j + 1] が真の場合

→ v[j + 1] >= v[j] が真の場合

code:exp3.10.2b.asm

slt $t0, $t4, $t3 # $t4 >= $t3 のとき $t0 = 0 ($t4 < $t3 のとき $t0 = 1)

beq $t0, $zero, exit2 # $t4 >= $t3 のとき exit2 へジャンプ

3) カウンタ繰り下げ

code:exp3.10.2b.asm

addi $s1, $s1, -1 # j = j - 1 (つまり j = j + (-1) )

4) ループの末尾から内側のループ(2番目の for ループ)の先頭に戻る

code:exp3.10.2b.asm

j for2tst # 内側の条件判定に戻る

exit2:

2番目の for ループをまとめると

code:exp3.10.2b-all.asm

addi $s1, $s0, -1 # j = i - 1 (つまり j = i + (-1) )

for2tst: slti $t0, $s1, 0 # $s1 < 0 (つまり j < 0 )のとき $t0 = 1

bne $t0, $zero, exit2 # $s1 < 0 (つまり j < 0 )のとき exit2 へジャンプ

add $t1, $s1, $s1 # $t1 = j * 2

add $t1, $s1, $s1 # $t1 = j * 4

add $t2, $a0, $t1 # $t2 = v + (j * 4)

# レジスタ $t2 は vj のアドレスを表す

lw $t3, 0($t2) # $t3 = vj

lw $t4, 4($t2) # $t4 = vj + 1

slt $t0, $t4, $t3 # $t4 >= $t3 のとき $t0 = 0 ($t4 < $t3 のとき $t0 = 1)

beq $t0, $zero, exit2 # $t4 >= $t3 のとき exit2 へジャンプ

...

(2番目の for ループの本体)

...

addi $s1, $s1, -1 # j = j - 1 (つまり j = j + (-1) )

j for2tst # 内側の条件判定に戻る

exit2:

sort 手続きからの swap 手続きの呼び出し

swap の呼び出しは、下記のように呼び出すだけ。簡単

code:exp3.10.3.asm

jal swap

sort 手続きから swap 手続きへのパラメータの引き渡し

一つの問題がある

一方では sort 手続き自体の呼び出しでレジスタ $a0, $a1 を使用してパラメータを引き渡す必要がある

sort(int v[], int n)

パラメータ v と n

レジスタ $a0 と $a1

ところが他方では同じレジスタを使用して swap 手続きにパラメータを引き渡す必要がある

swap(int v[], int k)

パラメータ v と k

レジスタ $a0 と $a1

解決策

sort 手続きの冒頭でレジスタ $a0 と $a1 を他のレジスタにコピーして、この2つのレジスタを swap 手続きの呼び出しに使用できるように空ける

引数レジスタ $a0 と $a1 を退避レジスタ $s2 と $s3 にコピーする

code:exp3.10.4.asm

move $s2, $a0 # $a0 を $s2 にコピー( sort 手続き用の第1パラメータ v[] を $s2 に退避)

move $s3, $a1 # $a1 を $s3 にコピー( sort 手続き用の第2パラメータ n を $s3 に退避)

swap 手続きにパラメータを渡す

code:exp3.10.5.asm

move $a0, $s2 # $s2 を $a0 にコピー( swap 手続き用の第1パラメータ v[] を渡す)

move $a1, $s1 # $s1 を $a1 にコピー( swap 手続き用の第2パラメータ j を渡す)

手続き呼び出し間でのレジスタの退避

レジスタの退避と復元

スタック

CODv2 第3章「命令：マシンの言葉」#6850f43e0000000000b18d30

退避、復元する必要があるレジスタ

戻りアドレスレジスタ $ra

退避レジスタ $s0, $s1, $s2, $s3

順番に、変数 i, j 、引数パラメータの退避と引渡 $a0, $a1

sort 手続きの冒頭で以下のようにレジスタの退避をおこなう

code:exp3.10.6.asm

addi $sp, $sp, -20 # スタック上にレジスタ5つ分の領域を確保する

sw $ra, 16($sp) # $ra をスタックに退避

sw $s3, 12($sp) # $s3 をスタックに退避

sw $s2, 8($sp) # $s2 をスタックに退避

sw $s1, 4($sp) # $s1 をスタックに退避

sw $s0, 0($sp) # $s0 をスタックに退避

sort 手続きの末尾でこれらの命令の逆を行いレジスタの復元を行う

呼び出し元に戻る

code:exp3.10.7.asm

jr $ra # 呼び出し元のルーチンへジャンプする(戻る)

sort 手続きの全体をまとめると

C コード

code:exp3.10.8.c

sort(int v[], int n)

{

int i, j;

for(i = 0; i < n; i = i + 1){

for(j = i - 1; j >= 0 && vj > vj + 1; j = j - 1){

swap(v, j);

}

アセンブリ・コード

code:exp3.10.8.asm

# レジスタの退避

sort: addi $sp, $sp, -20 # スタック上にレジスタ5つ分の領域を確保する

sw $ra, 16($sp) # $ra をスタックに退避

sw $s3, 12($sp) # $s3 をスタックに退避

sw $s2, 8($sp) # $s2 をスタックに退避

sw $s1, 4($sp) # $s1 をスタックに退避

sw $s0, 0($sp) # $s0 をスタックに退避

# パラメータのコピー

move $s2, $a0 # $a0 を $s2 にコピー( sort 手続きの第1パラメータ v[] を $s2 に退避)

move $s3, $a1 # $a1 を $s3 にコピー( sort 手続きの第2パラメータ n を $s3 に退避)

# 1番目の for ループ(前半)

move $s0, $zero # i =0

for1tst: slt $t0, $s0, $s3 # i >= n ($s0 >= $a1) のとき $t0 = 0

beq $t0, $zero, exit1 # i >= n ($s0 >= $a1) のとき exit1 へジャンプ

# 2番目の for ループ(前半)

addi $s1, $s0, -1 # j = i - 1 (つまり j = i + (-1) )

for2tst: slti $t0, $s1, 0 # $s1 < 0 (つまり j < 0 )のとき $t0 = 1

bne $t0, $zero, exit2 # $s1 < 0 (つまり j < 0 )のとき exit2 へジャンプ

add $t1, $s1, $s1 # $t1 = j * 2

add $t1, $s1, $s1 # $t1 = j * 4

add $t2, $s2, $t1 # $t2 = v + (j * 4) レジスタ $t2 は vj のアドレスを表す

lw $t3, 0($t2) # $t3 = vj

lw $t4, 4($t2) # $t4 = vj + 1

slt $t0, $t4, $t3 # $t4 >= $t3 のとき $t0 = 0 ($t4 < $t3 のとき $t0 = 1)

beq $t0, $zero, exit2 # $t4 >= $t3 のとき exit2 へジャンプ

# 2番目の for ループ(本体)

# パラメータの引渡

move $a0, $s2 # $s2 を $a0 にコピー( swap 手続きの第1パラメータ v[] を渡す)

move $a1, $s1 # $s1 を $a1 にコピー( swap 手続きの第2パラメータ j を渡す)

# swap 手続きの呼び出し

jal swap # swap 手続き

# 2番目の for ループ(後半)

addi $s1, $s1, -1 # j = j - 1 (つまり j = j + (-1) )

j for2tst # 内側の条件判定に戻る

# 1番目の for ループ(後半)

exit2: addi $s0, $s0, 1 # i = i + 1

j for1tst # 外側のループの最初に戻る

# レジスタの復元

exit1: lw $ra, 16($sp) # スタックから $ra を復元

lw $s3, 12($sp) # スタックから $s3 を復元

lw $s2, 8($sp) # スタックから $s2 を復元

lw $s1, 4($sp) # スタックから $s1 を復元

lw $s0, 0($sp) # スタックから $s0 を復元

addi $sp, $sp, 20 # スタック・ポインタを復元

# 呼び出し元への戻り

jr $ra # 呼び出し元のルーチンへジャンプする(戻る)